package unionfindset;

import java.util.Arrays;

public class UnionFindSet {

    public int[] elem;

    public UnionFindSet(int n) {
        elem = new int[n];
        Arrays.fill(elem, -1);
    }

    //查找双亲结点
    public int findRoot(int x) {
        if(x < 0 || x >= elem.length) {
            throw new IndexOutOfBoundsException("x 不合法");
        }
        while(elem[x] >= 0) {
            x = elem[x];
        }
        return x;
    }

    //判断两个元素是否在同一个集合中
    public boolean isSameSet(int x1, int x2) {
        if(findRoot(x1) == findRoot(x2)) {
            return true;
        }
        return false;
    }

    //将两个元素合并到同一个集合中
    public void union(int x1, int x2) {
        if(isSameSet(x1,x2)) {
            return;
        }
        int r1 = findRoot(x1);
        int r2 = findRoot(x2);
        elem[r1] += elem[r2];
        elem[r2] = r1;
    }

    //统计集合的个数
    public int setSizes() {
        int count = 0;
        for(int x : elem) {
            if(x < 0) {
                count++;
            }
        }
        return count;
    }
}
